iT邦幫忙

2024 iThome 鐵人賽

DAY 12
0
Software Development

全端實戰心法:小團隊的產品開發大小事系列 第 12

不寫演算法,也該懂的時間複雜度

  • 分享至 

  • xImage
  •  

有刷過題的工程師,一定都對時間複雜度不陌生,不過我卻遇過不少知道了時間複雜度這個概念,但是在日常的 Coding 中卻不知道怎麼運用的人。

我最常聽見的說法是:「產品中又不需要寫演算法,刷題和時間複雜度根本就用不上。」

然而,刷題用到的知識以及分析時間複雜度的能力在一般 Coding 真的用不到嗎?且讓我們看一個例子。

危險的 Build-in Function 陷阱

假設我們在前端實作一個簡單的功能:

印出所有商品名稱及其分類

const products = [
  { id: 1, name: 'Apple', categoryId: 1 },
  { id: 2, name: 'Carrot', categoryId: 2 },
  { id: 3, name: 'Orange', categoryId: 1 },
];
const categories = [
  { id: 1, name: 'Fruit' },
  { id: 2, name: 'Vegetable' },
];

例如以上資料,預期印出這樣的結果

Apple: Fruit
Carrot: Vegetable
Orange: Fruit

那麼該怎麼撰寫程式呢?我們先看以下這個例子

for (const product of products) {
  const categoryName = categories.find((category) => category.id === product.categoryId).name;
  console.log(`${product.name}: ${categoryName}`);
}

首先是走訪所有的商品,這沒有問題,但是再來獲取分類名稱的作法就有點問題了!

我們使用了 find() 這個 Array 的 Built-in Function,本質上就是走訪所有的 Categories,然後得到之中 id 與當前商品 categoryId 中一樣的元素。

也就是說,當我們走訪到每一個 Product 的時候,都會重新的走訪所有的 Categories,可以想像當 Categories 的數量越多的時候,程式所要走訪的元素就越多,複雜的程度將呈指數級的成長。

那麼這樣的寫法會怎麼樣的影響程式執行的 Performance 呢?我們就需要用「時間複雜度」分析一遍了。

時間複雜度 Time Complexity

所謂的時間複雜度,就是衡量一個演算法在時間效率上優劣的一種方法,我們通常用大寫的 O(讀作 Big-O)來表示。

下表就是不同類型的 Big-O,例如 O(1)、O(n)、O(n^2) 等等,括號裡的內容代表數據量為 n 的情況下,所需時間的成長趨勢,表格上面的 1,2,…,10 代表 n 的大小。

時間複雜度趨勢表格
*時間複雜度趨勢表格

例如 O(1) 代表常數的成長,不論數據量 n 有多大,所需的時間都不增加,所以在 O(1) 這個 row 的數值並不會因為數據量增加而有變化。當然這邊的不會增加是以數量級來衡量的,意味著就算有時間有增加,也不會是成倍、指數的增加。

而 O(n^2) 就是指數的增長了,可以從表格及下圖中明顯看到,當 n 的大小增大時,所需要的時間增加的趨勢快了許多,碾壓下面的 O(n), O(nlog(n)) 等等。

時間複雜度趨勢圖
*時間複雜度趨勢圖

迴圈加上 find() 函式

回到剛剛那個例子,我們在一個 for 迴圈當中呼叫了 Built-in function find(),該如何分析這個時間複雜度呢?

由於時間複雜度所評估的是資料變多造成的時間增長趨勢,我們需要先假設資料量:可以將 Products 的數量訂成 n,而 Categories 的數量為 m。

第一個 for 迴圈走訪了所有 Products,時間複雜度就是很直接的 O(n);而 find() 函式本質上也是另一個 for 迴圈,但是走訪了所有 Categories,所以時間複雜度是 O(m)。

解析演算法時間複雜度
*解析演算法時間複雜度

而我們每走訪到一個 Product,就跑一次 O(m):用其 Category ID 去反查 Category Name,也就是這整個演算法的時間複雜度是兩者的乘積 O(n) * O(m)。

我們如果假設 Products 和 Categories 的數量一樣都為 n,就可以簡化成 O(n) * O(n),等同於 O(n^2),一個指數型的增長。

當我們資料的數量不多時可能會感覺不出有什麼明顯的差異,但當數量變多時,這樣簡單的運算就可能讓你的瀏覽器速度變得極端緩慢!

實際計算看看,如果在迴圈中每跑一段 code 需要的時間是 1 µs(百萬分之一秒),當 n 的數量為 100 時,只要約 10 ms(10,000 µs)的時間便能跑完,人體幾乎感受不到。

但是當 n 的數量成長成 1,000 時,就需要 1 秒才能跑完,已經是我們能感受到的時間了;若 n 為 2,000 時,就要 4 秒、3,000 需要 9 秒,而這僅僅是一個從產品找類別的簡單演算而已。

在程式開發的初期如果因為測試的資料量少,而忽略這個問題,很可能就會在產品實際上線時發覺怎麼速度越來越慢了。這也就是為什麼工程師該知道一些時間複雜度,就算我們並不會實際撰寫高深的演算法,還是需要知道我們所使用的 function 會對整個產品的效能造成什麼影響。

接下來讓我們來聊聊在全端開發常用的資料結構,什麼時候使用它們,又如何分析他們的時間複雜度。


上一篇
何謂 CORS?網站開發該懂的網路知識
下一篇
全端資結入門(一),Array 之操作時間複雜度:讀取、搜尋、插入、刪除
系列文
全端實戰心法:小團隊的產品開發大小事30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言